package hw03;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class Utils {
	
	public static boolean trace = false;
	
	public static void trace(Object o) {
		if(trace) {
			System.out.println(o);
		}
	}
	
	public static Set<RelationalSignature> decomposeInto3NF(RelationalSignature R, Set<FunctionalDependency> F) {
		Set<RelationalSignature> result = new HashSet<RelationalSignature>();
		Set<FunctionalDependency> G = Utils.minimalBasis(F);
		boolean foundSuperKey = false;
		for(FunctionalDependency FD : G) {
			Set<Attribute> XA = new TreeSet<Attribute>();
			XA.addAll(FD.getLeft());
			XA.addAll(FD.getRight());
			boolean accountedFor = false;
			for(RelationalSignature existing : new TreeSet<RelationalSignature>(result)) {
				if(existing.getAttributes().containsAll(XA)) {
					accountedFor = true;
					break;
				} else if(XA.containsAll(existing.getAttributes())) {
					result.remove(existing);
					break;
				}
			}
			if(!accountedFor) {
				result.add(R.decompose(XA));
			}
			if(!foundSuperKey) {
				foundSuperKey = Utils.closure(XA, F).containsAll(R.getAttributes());
			}
		}
		if(!foundSuperKey) {
			result.add(R.decompose(Utils.key(R, F)));
		}		
		return result;
	}

	public static Set<RelationalSignature> decomposeIntoBCNF(RelationalSignature R0, Set<FunctionalDependency> S) {
		Set<RelationalSignature> result = new HashSet<RelationalSignature>();
		FunctionalDependency XY = bcnfViolation(R0, S);
		if(XY == null) {
			result.add(R0);
		} else {
			Set<Attribute> closureX = Utils.closure(XY.getLeft(), S);
			Set<Attribute> notClosureX = new TreeSet<Attribute>();
			notClosureX.addAll(R0.getAttributes());
			notClosureX.removeAll(closureX);
			notClosureX.addAll(XY.getLeft());
			RelationalSignature R1 = R0.decompose(closureX);
			RelationalSignature R2 = R0.decompose(notClosureX);
			Set<FunctionalDependency> S1 = Utils.projectDependencies(R0, R1, S);
			Set<FunctionalDependency> S2 = Utils.projectDependencies(R0, R2, S);
			result.addAll(decomposeIntoBCNF(R1, S1));
			result.addAll(decomposeIntoBCNF(R2, S2));
		}
		return result;
	}
	
	public static FunctionalDependency bcnfViolation(RelationalSignature R, Set<FunctionalDependency> S) {
		for(FunctionalDependency FD : S) {
			if(R.getAttributes().containsAll(FD.getLeft())) {
				if(!Utils.closure(FD.getLeft(), S).containsAll(R.getAttributes())) {
					return FD;
				}
			}
		}
		return null;
	}
	

	public static Set<RelationalSignature> decomposeInto4NF(RelationalSignature R0, Set<MultivaluedDependency> S0) {
		// TODO Auto-generated method stub
		return null;
	}
	
	public static MultivaluedDependency fnfViolation(RelationalSignature R, Set<MultivaluedDependency> S) {
		for(MultivaluedDependency MVD : S) {
			if(R.getAttributes().containsAll(MVD.getLeft())) {
				if(!Utils.closure(MVD.getLeft(), S).containsAll(R.getAttributes())) {
					return MVD;
				}
			}
		}
		return null;
	}

	public static Set<Attribute> key(RelationalSignature R, Set<FunctionalDependency> S) {
		Set<Attribute> key = new TreeSet<Attribute>(R.getAttributes());
		for(FunctionalDependency FD : S) {
			if(key.containsAll(FD.getLeft())) {
				key.removeAll(FD.getRight());
			}
		}
		return key;
	}
	
	public static Set<FunctionalDependency> minimalBasis(Set<FunctionalDependency> S) {
		Set<FunctionalDependency> B = new TreeSet<FunctionalDependency>();
		for(FunctionalDependency FD : S) {
			B.addAll(FD.split());
		}
		for(FunctionalDependency FD : new TreeSet<FunctionalDependency>(B)) {
			Set<FunctionalDependency> notFD = new TreeSet<FunctionalDependency>(B);
			notFD.remove(FD);
			if(FD.followsFrom(notFD)) {
				B.remove(FD);
			}
		}
		return B;
	}
	
	public static Set<Attribute> closure(Set<Attribute> A, Set<? extends Dependency> S) {
		Set<Attribute> X = new TreeSet<Attribute>(A);
		Iterator<? extends Dependency> dIter = S.iterator();
		while(dIter.hasNext()) {
			Dependency d = dIter.next();
			if(X.containsAll(d.getLeft()) && !X.containsAll(d.getRight())) {
				X.addAll(d.getRight());
				dIter = S.iterator();
			}
		}
		return X;
	}
	
	public static Set<FunctionalDependency> projectDependencies(RelationalSignature R, RelationalSignature R1, Set<FunctionalDependency> S) {
		Set<FunctionalDependency> T = new TreeSet<FunctionalDependency>();
		for(Set<Attribute> X : subsets(R1.getAttributes())) {
			for(Attribute A : closure(X, S)) {
				if(R1.getAttributes().contains(A) && !X.contains(A)) {
					T.add(new FunctionalDependency(X, A));
				}
			}
		}
		Iterator<FunctionalDependency> fdIter = T.iterator();
		while(fdIter.hasNext()) {
			FunctionalDependency FD = fdIter.next();
			Set<FunctionalDependency> others = new TreeSet<FunctionalDependency>(T);
			others.remove(FD);
			if(FD.followsFrom(others)) {
				T.remove(FD);
				fdIter = T.iterator();
			} else if(FD.getLeft().size() >= 2) {
				Set<Attribute> Y = FD.getLeft();
				Set<Attribute> B = FD.getRight();
				for(Attribute A : Y) {
					Set<Attribute> Z = new TreeSet<Attribute>(Y);
					Z.remove(A);
					FunctionalDependency ZB = new FunctionalDependency(Z, B);
					if(ZB.followsFrom(T)) {
						T.remove(FD);
						T.add(ZB);
						fdIter = T.iterator();
						break;
					}
				}
			}
		}
		return T;
	}

	public static Set<Set<Attribute>> subsets(Set<Attribute> set) {
		Set<Set<Attribute>> subsets = new HashSet<Set<Attribute>>();
		if (set.size() == 0) {
			subsets.add(new TreeSet<Attribute>());
		} else {
			TreeSet<Attribute> tail = new TreeSet<Attribute>(set);
			Attribute head = tail.first();
			tail.remove(head);
			subsets.addAll(subsets(tail));
			for(Set<Attribute> subset : subsets(tail)) {
				subset.add(head);
				subsets.add(subset);
			}
		}
		return subsets;
	}

	public static Set<RelationalSignature> join(Set<RelationalSignature> S) {
		Set<RelationalSignature> result = new TreeSet<RelationalSignature>();
		for(RelationalSignature R : S) {
			boolean added = false;
			for(RelationalSignature existing : result) {
				if(existing.getSource().equals(R.getSource())) {
					existing.getAttributes().addAll(R.getAttributes());
					existing.setAttributes(existing.getAttributes());
					added = true;
					break;
				}
			}
			if(!added) {
				R.resetDecomp();
				result.add(R);
			}
		}
		return result;
	}
	
}
